Leetcode 84. Largest Rectangle in Histogram 题解

题目链接

Leetcode 84. Largest Rectangle in Histogram

题目内容

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Example:

Input: [2,1,5,6,2,3]

Output: 10

解题思路

这个题目的最简单的思路肯定就是dp了，但是毫无疑问使用dp的话，时间复杂度肯定会超。这题比较好的方法就是使用栈来构造一个升序序列，首先，如果我们的height数组是升序的话，以1, 2, 3, 4, 5为例，我们就可以取最大面积$$max(15, 24, 33, 42, 5*1)= 9$$，我们使用栈的目的也是为了构建这么一个升序队列，我们的构建方法就是:

首先height[0]进栈，然后对每一个后面的height判断是否满足升序，若满足则push进栈继续，若不满足，则弹出部分元素，直到满足升序条件，并在弹出过程中计算面积与我们的面积比较，维护我们的最大面积，满足后将弹出的元素替换成当前的height继续操作，构建完成后，按照我们以上说的升序序列求最大面积的计算方法再跟之前我们维护的最大面积比较，我们就能得出我们的最大面积了。

提交的时间复杂度如下:

题目代码

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int area = 0;
        stack<int> tmp;
        for (int i = 0; i < height.size(); i++) {
            if  (tmp.empty() || tmp.top() <= height[i])
                tmp.push(height[i]);
            else {
                int length = 0;
                while (!tmp.empty() && tmp.top() > height[i]) {
                    ++length;
                    area = max(area, tmp.top()*length);
                    tmp.pop();
                }
                while (length--)
                    tmp.push(height[i]);
                tmp.push(height[i]);
            }
        }
        int length = 1;
        while (!tmp.empty()) {
            area = max(area, tmp.top()*length);
            tmp.pop();
            ++length;
        }
        return area;
    }
};